package day_2022_9_to_12.Day;

/**
 * @author haomin
 * @date 2022/11/19 08:59
 **/
public class Day74_1_Num891_SumSubseqWidths {
    class Solution {
        int mod=(int)1e9+7;
        public int sumSubseqWidths(int[] nums) {
            long pow[]=new long[100005];
            pow[0]=1;
            for(int i=1;i<=100000;i++){pow[i]=pow[i-1]*2%mod;}
            int count[]=new int[100005];
            for(int i=0;i<nums.length;i++){count[nums[i]]++;}
            long maxSum=0,minSum=0;
            int num=0;
            for(int i=1;i<=100000;i++){
                if(count[i]==0){continue;}
                maxSum=(maxSum+pow[num]*(pow[count[i]]-1)%mod*i)%mod;
                num+=count[i];
            }
            num=0;
            for(int i=100000;i>0;i--){
                if(count[i]==0){continue;}
                minSum=(minSum+pow[num]*(pow[count[i]]-1)%mod*i)%mod;
                num+=count[i];
            }
            return (int)(maxSum-minSum+mod)%mod;
        }
    }
}